package fun.ticsmyc.question;

public class 二分找两个有序数组第k大 {

    /**
     * 每次可以去掉 K/2个小数，直到k=1或某个数组为空
     */

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length+nums2.length;
        if(len %2 ==0){
            double v = find(nums1, 0,nums2,0, len / 2);
            double v1 = find(nums1,0, nums2,0, len / 2 + 1);
            return (v+v1)/2;
        }else{
            return find(nums1,0,nums2,0,len/2 +1);
        }
    }

    private double find(int[] nums1,int l1, int[] nums2,int l2, int i) {
        if(nums1 == null || nums1.length==l1){
            return nums2[l2+i-1];
        }
        if(nums2 ==null || nums2.length == l2){
            return nums1[l1+i-1];
        }
        if(i == 1){
            return Math.min(nums1[l1],nums2[l2]);
        }
        int del = i/2;
        int newLIndex = Math.min(l1+del-1,nums1.length-1);
        int newRIndex = Math.min(l2+del-1,nums2.length-1);
        if(nums1[newLIndex] < nums2[newRIndex]){

            return find(nums1,newLIndex+1,nums2,l2,i-(newLIndex-l1+1));
        }else{
            return find(nums1,l1,nums2,newRIndex+1,i-(newRIndex-l2+1));
        }
    }

}
